Listes et chaînes de caractères

Table des matières

1. Listes

Le type list en Python permet de travailler avec une liste d'objets. Elle est représentée par la liste de ces objets, encadrée par des crochets, par exemple : [1,2,3]. La liste vide ne contenant aucun objet est notée [].

Ces objets peuvent être des entiers, des flottants, ou même d'autres listes. Habituellement, tous les objets d'une liste sont du même type, mais ce n'est pas forcément le cas. 

In [1]: a = [1,2,3]

In [2]: type(a)
Out[2]: list

In [3]: b = ["a","ab","abc"]

In [4]: type(b)
Out[4]: list

In [5]: c = [1, "abc", [1,2,3]]
# La liste c contient 3 objets
In [6]: type(b)
Out[6]: list

On peut tester si une liste l est vide via l == [] ou len(l) == 0.

1.1. Indexation

La fonction len (pour length) permet de déterminer la longueur d'une liste (c'est-à-dire son nombre d'éléments).

On peut accéder au $i$−ème caractère d'une liste l par l'indexation l[i-1] (pour $i$ inférieur ou égal à la longueur de la chaîne). En informatique l'indexation commence toujours par $0$. Le premier élément d'une liste est à l'indice $0$, et le dernier élément d'une liste de longueur $\l$ est à l'indice $\l-1$. 

In [1]: l = [0] * 8
# Création d'une liste de 0
In [2]: l
Out[2]: [0, 0, 0, 0, 0, 0, 0, 0]
In [3]: len(l)
Out[3]: 8

In [4]: lc = [1,4,9,16]
# Liste des carrés
In [5]: lc[0]
Out[5]: 1
In [6]: lc[len(lc)-1]
Out[6]: 16

In [7]: s = 0
# On calcule la somme des carrés :
In [8]: for e in lc:
   ...:     s += e
   ...: s
Out[8]: 30 # 1+4+9+16

Écrire une fonction qui prend en argument une liste l et qui renvoie True si la liste est non vide, et si ses premier et dernier éléments sont égaux, et False sinon.

On peut indexer une liste par des entiers négatifs : l[-1] renvoie le dernier caractère, l[-2] l'avant-dernier, etc.

1.2. Itération

Il y a deux façons d'itérer sur les éléments d'une liste l, ou bien sur les indices, avec for i in range(len(l)), ou bien sur les valeurs, avec for e in l. Les deux extraits suivants sont équivalents, et affichent tous les éléments d'une liste l. 

# i prend les valeurs de 0 à \texttt{len(l)} − 1
for i in range(len(l)):
    print(l[i])

# e prend toutes les valeurs des éléments de \texttt{l}
for e in l:
    print(e)

Écrire une fonction somme qui prend en argument une liste l et renvoie la somme de ses éléments. On écrira deux versions, une en utilisant une boucle for e in l et une autre en utilisant for i in range(...).

Écrire une fonction appartient qui prend deux arguments : un élément e et une liste l et qui renvoie True si l'élément appartient à la liste, et False sinon.

Dans le pire des cas, la fonction précédente réalise $n$ comparaisons, où $n$ est la longueur de la liste. On dit que la complexité est linéaire.

Pour tester si un élément appartient à une liste, on peut directement utiliser l'instruction e in l qui renvoie True si e appartient à l et False sinon. Pour évaluer cette expression, Python procède comme pour la fonction appartient écrite plus haut. En particulier, la complexité est linéaire.

Écrire une fonction qui prend en argument une liste non vide et renvoie le premier indice i pour lequel l[i] > l[0]. Si un tel indice n'existe pas, on renverra la valeur spéciale None.

Recherche du minimum

Les fonctions suivantes prennent en argument une liste non vide d'entiers ou de flottants.

  1. Écrire une fonction minimum qui renvoie l'élément minimum de la liste.

    On utilisera une variable m, initialisée à l[0]. Caractériser la valeur de m au fil de l'exécution.

  2. Sans utiliser minimum, écrire une fonction premier_indice_min qui renvoie le premier indice où le minimum est atteint, et une variante dernier_indice_min.

  3. Écrire une fonction unique_minimum qui renvoie True ssi l'élément minimum de la liste n'est présent qu'une unique fois.

    On pourra proposer une deuxième implémentation qui ne parcourt la liste qu'une seule fois.

Étant donnés $n\geq 2$ et $x_1,\dots,x_n$ des nombres, on s'intéresse à la quantité $\max (|x_1-x_2|, |x_2-x_3|, \dots, |x_{n-1}-x_n|)$. Écrire une fonction plus_grand_ecart qui prend en argument une liste l de nombres et qui renvoie cette quantité, ou la valeur spéciale None si la longueur de la liste est $\leq 1$.

On veut écrire une fonction deuxieme_max qui prend en argument une liste l non vide d'entiers et qui renvoie, s'il existe, le plus grand élément qui soit strictement inférieur au maximum de la liste l. S'il n'existe pas, on renverra None.

  1. Écrire un jeu de tests.
  2. En utilisant la fonction max, implémenter la fonction demandée. On pourra initialiser une variable à la valeur None.
  3. Proposer une nouvelle implémentation dmax qui ne parcourt la liste qu'une seule fois.
  4. Écrire une variante dmax_bis qui renvoie le maximum si la liste contient au moins deux fois cet élément, avec un seul parcours.

Autres renvois d'une quantité booléenne

Écrire une fonction respecte_parite qui prend en argument une liste l d'entiers et renvoie True si les éléments d'indices pairs de l sont pairs et les éléments d'indices impairs de l sont impairs.

Écrire une fonction est_croissante qui prend en argument une liste d'entiers l et renvoie True si la liste est triée par ordre croissant, et False sinon. Par convention, la liste vide est croissante.

Écrire une fonction est_monotone qui prend en argument une liste d'entiers l et renvoie True si la liste est triée par ordre croissant ou par ordre décroissant, et False sinon. Par convention, la liste vide est monotone. Écrire une seconde version qui ne parcours la liste qu'une seule fois.

1.3. Modification et création de listes

On peut modifier une liste. Les opérations élémentaires sont la modification du $i$−ème élément d'une liste, l'ajout d'un élément e à la fin de la liste (append) et le retrait d'un élément à la fin de la liste (pop).

Ces dernières (append et pop) sont des méthodes plutôt que des fonctions. Si l est une liste, on les appelle par la syntaxe l.append(e) et l.pop(). Ces méthodes modifient la liste l, append ne renvoie rien et pop renvoie l'élément retiré. 

In [1]: l = [1,2,3] # Création d'une liste

In [2]: l[1] = 4    # On modifie le deuxième élément

In [3]: l
Out[3]: [1, 4, 3]

In [4]: l.append(2) # On ajoute un élément à la fin


In [5]: l
Out[5]: [1, 4, 3, 2]

In [6]: l.pop() # On retire un élément à la fin
Out[6]: 2       # L'élément est renvoyé

In [7]: l       # la liste a été modifiée
Out[7]: [1, 4, 3]

Construction de listes

À l'aide d'appels append successifs, construire la liste

  1. des 100 premiers carrés d'entiers naturels (c'est-à-dire les $n^2$, pour $n\in\N$).
  2. des entiers naturels $\leq 100$ qui ne sont pas divisibles par $3$.

  3. des 100 premiers nombres triangulaires qui ne sont pas divisibles par $3$.

    Les nombres triangulaires sont les nombres de la forme $\frac{n(n+1)}{2}$, pour $n\in\N$.

Les deux premières listes de l'exercice précédents peuvent être créées par les instructions suivantes qui utilisent une syntaxe spéciale pour la création de listes, dite en compréhension.

  • [k**2 for k in range(100)]
  • [k for k in range(101) if k % 3 != 0]

Écrire une fonction sommes_partielles qui prend en argument une liste $\texttt{l} = [x_1,\dots,x_n]$ de longueur n et renvoie une nouvelle liste de longueur n contenant les $S_k = \sum_{i=1}^k x_i$.

assert(sommes_partielles([1,2,4]) == [1,3,7]))

Construire la liste de taille 100 suivante : l = [1,2,2,3,3,3,4,4,4,4,...].

Suppression d'un élément

Écrire une fonction supprime_ind qui prend en argument une liste l et un indice i et modifie la liste l, en supprimant et renvoyant l'élément présent à l'indice i, et préservant l'ordre des autres éléments de l. Quelle est la complexité de votre fonction ?

Cette fonctionnalité est déjà implémentée en Python, sous la forme d'un argument facultatif à la méthode pop : l'instruction l.pop(i) retire et renvoie l'élément d'indice i de l. Elle a une complexité linéaire.

  1. Écrire une fonction with_removed qui prend en argument un élément e et une liste l et qui renvoie une nouvelle liste, contenant les mêmes éléments que l, mais en retirant toutes les occurrences de e.
  2. Écrire une fonction remove qui prend en argument un élément e et une liste l et qui modifie la liste l en lui retirant toutes les occurrences de e.

Échange d'éléments

Si l est la liste [3,5]. Que vaut-elle après l'exécution des extraits suivants ? 

l = [3,5]
l[0] = l[1]
l[1] = l[0]
# l = ??


l = [3,5]
z = l[0]
l[0] = l[1]
l[1] = z
# l = ??

Le deuxième extrait permet donc d'échanger les valeurs de l aux indices $0$ et $1$.

Plus concise, l'instruction l[i], l[j] = l[j], l[i] permet d'échanger les deux éléments d'indice i et j de la liste l, sans utiliser de variable intermédiaire. Les deux extraits suivants sont équivalents. 

z = l[0]
l[0] = l[1]
l[1] = z

l[0], l[1] = l[1], l[0]

Écrire une fonction renverse qui prend en argument une liste l et la modifie en inversant l'ordre de ses éléments : Si l=[1,2,3,4], l'appel de la fonction renverse(l) la modifie en [4,3,2,1]. La fonction renverse ne renverra rien.

Cette fonctionnalité est déjà présente en Python sous la forme d'une méthode reverse. Si l est une liste, l'appel l.reverse() modifie la liste l comme la fonction précédente.

Écrire une fonction miroir qui prend en argument une liste l et renvoie une nouvelle liste, contenant les mêmes éléments que l, mais dans l'ordre inverse. On ne modifiera pas la liste donnée en argument, et on ne la copiera pas.

assert(miroir([1,2,3,4]) == [4,3,2,1]).

Copie d'une liste

Pour copier une liste, il faut utiliser l'instruction lbis = l.copy() plutôt que lbis = l.

La fonction miroir précédente peut être implémentée de la façon suivante : 

def miroir(l):
    lbis = l.copy()
    lbis.reverse() # modifie lbis
    return lbis

Ne pas utiliser l'instruction lbis = l pour copier une liste. Après cette instruction, lbis et l pointent vers la même liste en mémoire, et toute modification sur l'une de ces variables modifie également l'autre. 

In [1]: l = [1,2,3]
In [2]: lbis = l       # pas une vrai copie
In [3]: lbis.append(4) # on modifie lbis
In [4]: l
Out[4]: [1, 2, 3, 4]   # l a été modifiée !

In [1]: l = [1,2,3]
In [2]: lbis = l.copy()
In [3]: lbis.append(4)
In [4]: l
Out[4]: [1, 2, 3] # l n'a pas été modifiée

Concaténation

L'opérateur + permet de concaténer deux listes. 

In [1]: [1,2,3] + [4, 5, 6]
Out[1]: [1,2,3,4,5,6]

  1. Réimplémenter la concaténation, sous la forme d'une fonction concatene qui prend en argument deux listes, et en renvoie une nouvelle.

    Quel est le nombre d'opérations élémentaires effectuées, en fonction des longueurs des deux listes ?

  2. Écrire une fonction etendre qui prend en argument deux listes l1 et l2 et qui modifie la première liste, en lui rajoutant à la fin les éléments de la seconde, dans le même ordre. Si l=[1,2,3], après l'appel etendre(l,[4,5]), la liste l vaudra [1,2,3,4,5].

    Quel est le nombre d'opérations élémentaires effectuées ?

Les instructions l.append(2) et l=l+[2] semblent avoir le même effet, mais il faut privilégier la première.

La seconde crée une nouvelle liste : si la liste l a un million d'éléments à l'origine, l'instruction l = l + [2] va recopier entièrement la liste (avec son million d'éléments), lui rajouter 2 à la fin, et affecter cette nouvelle liste à la variable l, alors que l'instruction l.append(2) effectue (essentiellement) une unique opération.

Pour ajouter un élément au début de la liste l, on peut ou bien utiliser l = [2] + l, ou utiliser une boucle pour décaler tous les éléments de l. Dans les deux cas, cette opération est coûteuse (au même titre que l = l + [2]). Pour cette raison, il vaut mieux éviter de concevoir des algorithmes qui ajoutent des éléments au début d'une liste.

2. Chaînes de caractères

En Python, l'objet "Hello World" est une chaîne de caractères, de type str (pour string en anglais). Une chaîne de caractères est formée d'une suite de caractères, encadrés par des guillemets, ou des apostrophes. La chaîne "", qui ne contient aucun caractère, est appelée la chaîne vide. 

In [1]: "Hello World"
Out[1]: 'Hello World'

In [2]: type("Hello World")
Out[2]: str

In [3]: print("Hello World")
Hello World

Le caractère \ est utilisé pour «échapper» («escape» en anglais) d'autres caractères :

  • Pour représenter un retour à la ligne, utiliser le caractère spécial \n.
  • Pour représenter le caractère " dans une chaîne délimitée par des guillemets, il faut utiliser \".
  • Pour représenter le caractère \ dans une chaîne de caractère, il faut utiliser \\.
In [1]: print("Hello\nWorld")
Hello
World

In [2]: print("Hello \"World\"")
Hello "World"


In [3]: print("Un antislash : \\")
Un antislash : \

Par défaut, la fonction print rajoute un retour à la ligne "\n" à la fin de ce qu'elle imprime. Ce comportement peut être changé en donnant une autre valeur à l'argument facultatif end. 

In [1]: print("Hello"); \
   ...: print("World")
Hello   # retour à la ligne
World

In [2]: print("Hello", end=""); \
   ...: print("World")
HelloWorld


In [2]: print("Hello", end=" "); \
   ...: print("World")
Hello World

2.1. Construction de chaînes

2.1.1. Concaténation

L'opérateur + permet de concaténer (= coller) des chaînes de caractères : 

In [1]: "" + "Hello" + " " + "World"
Out[1]: "Hello World"

L'opérateur * permet de répéter une chaîne plusieurs fois : 

In [2]: "Hello" * 3
Out[2]: "HelloHelloHello"

In [3]: "#" * 30
Out[3]: "##############################"

Écrire des fonctions prenant un entier $n$ en argument et affichant les figures ci-dessous, de taille $n$. 

In [1]: triangle1(5)
*
**
***
****
*****

In [2]: triangle2(5)
*****
****
***
**
*

In [3]: triangle3(5)
    *
   **
  ***
 ****
*****

Écrire une fonction croix prenant un entier $n$ en argument et imprime la figure ci-contre, de taille $n$. On utilisera deux boucles imbriquées. 

In [4]: croix(9)
  * * * * * * *
*   * * * * *   *
* *   * * *   * *
* * *   *   * * *
* * * *   * * * *
* * *   *   * * *
* *   * * *   * *
*   * * * * *   *
  * * * * * * *

2.1.2. Conversion de types

On peut obtenir une chaîne de caractères représentant l'écriture décimale d'un entier (ou d'un flottant) grâce à la fonction str : 

In [1]: str(123)
Out[1]: "123"

In [1]: str(7**7)
Out[1]: "823543"

Dans l'autre sens, on peut transformer une chaîne représentant une écriture décimale en un entier en utilisant int. Cette conversion de type peut échouer. 

In [1]: a = str(123)
# a = "123"
In [2]: b = str(456)
# b = "456"
In [3]: int(a+b)
Out[3]: 123456
# a+b = "123456"

In [4]: int("abc")
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-4-2dda1cc00c48> in <module>
----> 1 int("abc")

ValueError: invalid literal for int() with base 10: 'abc'

Écrire une fonction cinq_fois qui prend en entrée un entier n et renvoie l'entier m dont l'écriture décimale est de la forme $xxxxx$ où $x$ est l'écriture décimale de $n$.

  • assert(cinq_fois(3) == 33333)
  • assert(cinq_fois(12) == 1212121212)

Opérateur in

On peut tester si une chaîne de caractère est une sous-chaîne d'une autre chaîne grâce à l'opérateur in :

  • assert("jour" in "Bonjour")
  • assert(not("baba" in "bambou"))

Déterminer le plus petit entier $n$ tel que l'écriture décimale de $2^n$ contienne votre année de naissance.

2.2. Indexation

La fonction len et l'indexation fonctionnent comme pour les listes. Si c est une chaîne, l'indexation c[i] renvoie une chaîne, contenant un seul caractère. 

In [1]: a = "Bonjour"

In [2]: len(a)
Out[2]: 7


In [3]: a[0]
Out[3]: "B"

In [4]: a[6]
Out[4]: "r"

In [5]: a[7]
----------------------------------------------------------------

IndexError: string index out of range

Compléter les extraits suivants, avec ce que renvoient les instructions. 

In [1]: a = "Salut"
In [2]: a[3] + a[2] + a[1]
Out[2]:


In [3]: b = "A B CD"
In [4]: b[1] + b[3] + b[5]
Out[4]:


In [5]: b[len(a)]
Out[5]:
In [6]: b[len(b)-1]
Out[6]:

En Python les chaînes de caractères sont immutables : contrairement aux listes de la partie suivante, il n'est pas possible de modifier un caractère particulier dans la chaîne, ou de l’agrandir. Dans le premier cas, il faut construire une nouvelle chaîne et dans le second, les opérateurs de concaténation créent également une nouvelle chaîne.

Écrire une fonction str_egales qui prend en arguments deux chaînes de caractères c1, c2 et qui renvoie True si elles sont égales. Quel est, en fonction des longueurs $\l_1$ et $\l_2$ de c1 et c2, le nombre de comparaison effectuées dans le pire des cas ?

En fait, on peut tester l'égalité de deux chaînes de caractères avec l'instruction c1 == c2. Cette instruction a une complexité linéaire en le minimum des longueurs, comme l'implémentation précédente.

On imagine la chaîne de caractère infinie "12345678910111213...". Déterminer le millionième chiffre (caractère) de cette chaîne.

Itération sur les caractères d'une chaîne

On peut écrire une boucle qui énumère les caractères d'une chaîne des deux façons équivalentes suivantes. 

ch = "Bonjour" # Chaîne de longueur ł
for i in range(len(ch)): # i∞n\db{0,ł−1}
    print(ch[i])

ch = "Bonjour"
for car in ch: # car prend les valeurs "B", "o", ...
    print(car)

  1. Écrire une fonction indice_lettre qui prend en arguments deux chaînes de caractères, la deuxième étant une lettre et qui renvoie le premier indice où la lettre se trouve dans le mot. Si le mot ne contient pas cette lettre, on renverra une la valeur particulière None en utilisant l'instruction return None, ce qui revient à ne pas mettre d'instruction return.
  • assert(indice_lettre("Bonjour", "o") == 1).
  • assert(indice_lettre("Bonjour", "a") == None)

  1. Écrire une fonction indice_lettre_bis, qui renvoie le dernier indice.
  2. Écrire une fonction liste_indices qui renvoie la liste des indices.

Écrire une fonction affiche_miroir qui prend en argument une chaîne de caractères et affiche les caractères de la chaîne, dans l'ordre inverse : affiche_miroir("Bonjour") affichera ruojnoB. On utilisera des appels de la forme print(char, end=""), pour éviter l'ajout de retour à la ligne (caractère \n).

2.3. Exercices

Écrire une fonction long_prefixe_commun qui prend en argument deux chaînes de caractères et renvoie la longueur du plus long préfixe commun.

assert(long_prefixe_commun("Bonjour", "Bonsoir") == 3) : le plus long préfixe commun est "Bon".

  1. Écrire une fonction palindrome qui prend en argument une chaîne de caractères et renvoie True si c'est un palindrome et False sinon. Un palindrome est une chaîne de caractères qui peut se lire indifféremment de gauche à droite ou de droite à gauche, comme les mots "kayak" et "ressasser".
  2. ★ Écrire une seconde version, qui marche également pour des phrases avec des espaces. Par exemple "engage le jeu que je le gagne" est un palindrome.

Écrire une fonction vacances qui prend en entrée une chaîne de caractères représentant une date au format jj/mm/aaaa, et qui renvoie True si cette date est pendant les vacances d'été (du premier juillet au 31 août), et False sinon.

  • assert(vacances("15/07/2022"))
  • assert(not(vacances("30/06/2022")))

Écrire une fonction avant_dict qui prend en argument deux chaînes de caractères et qui renvoie True si la première précède la seconde pour l'ordre du dictionnaire, et False sinon.

Pour comparer l'ordre de deux lettres, on utilisera la fonction ord qui associe à chaque lettre un entier. Si a et b sont deux lettres, l'instruction ord(a) <= ord(b) donne True si et seulement si la lettre a précède b dans l'ordre alphabétique : assert(ord("a") < ord("b")).

En fait, les opérateurs de comparaison <,>,<=,>= fonctionnent pour des chaînes de caractères, et correspondent à l'ordre lexicographique du dictionnaire.

3. Autres parcours sur les listes

3.1. Parcours quadratiques

Écrire une fonction aucun_doublon qui prend en argument une liste et renvoie True si cette liste ne contient pas deux fois le même élément.

Si la liste est de longueur $n$, combien de comparaisons effectuez-vous dans le pire des cas ? Essayer d'optimiser (sans trier la liste).

Étant données deux listes $\texttt{l}_1$ et $\texttt{l}_2$ contenant chacune des éléments distincts.

  1. Écrire une fonction nb_elems_communs qui renvoie le nombre d'éléments en commun de ces deux listes.

    Quelle est la complexité en fonction des longueurs $n_1$ et $n_2$ des deux listes ?

  2. ★ Sous l'hypothèse supplémentaire que les deux listes soient triées par ordre croissant, écrire une nouvelle version de la fonction précédente, avec une complexité linéaire.

Écrire une fonction produit_max qui prend en argument une liste de longueur $\geq 2$ et qui renvoie la valeur maximale du produit de deux éléments de la liste d'indices distincts. Quel est le nombre (en ordre de grandeur) d'opérations effectuées par votre algorithme, en fonction de la longueur $n$ de la liste ?

assert(produit_max([1,5,3,4,1]) == 20).

Utilisation naïve d'une liste comme ensemble

  1. Écrire une fonction collection qui prend en argument une liste l et qui renvoie une nouvelle liste, qui contient les mêmes éléments que la liste l, mais sans doublons. Préciser la complexité de votre implémentation (éventuellement dans le pire des cas), en fonction de la longueur $n$ de la liste l.
  2. Sous l'hypothèse supplémentaire que tous les éléments de la liste appartiennent à $\db{0,100}$, écrire une nouvelle version qui réalise de l'ordre de $n + 100$ opérations.

3.2. Parcours linéaires non triviaux

Écrire une fonction longueur_degarnie qui prend en argument une liste l et qui renvoie la longueur de la liste obtenue en retirant tous les $0$ au début et à la fin de l.

assert(longueur_degarnie([0, 0, 1, 2, 0, 5, 0]) == 4)

Une suite finie $x_1,\dots,x_n$ est dite unimodale s'il existe un indice $k\in\db{1,n}$ tel que $x_1,\dots,x_k$ soit croissante et $x_k,\dots,x_n$ soit décroissante.

Écrire une fonction unimodale qui prend en argument une liste et renvoie True ssi la suite de valeurs qu'elle représente est unimodale.

Écrire une fonction longueur_max_plateau qui prend en argument une liste et renvoie le plus grand entier $k$ tel que la liste contienne $k$ éléments consécutifs égaux. On veut une implémentation avec une complexité linéaire.

assert(longueur_max_plateau([0,1,1,1,0,0,1,0]) == 3).

Le relief d'une montagne est représenté par une liste des altitudes $\texttt{l} = [\l_0, \dots, \l_{n-1}]$ tous les 100 mètres. Un promeneur avec un parapente est situé à l'indice $i$, donc à l'altitude $\l_i$. On dit qu'un indice $k\in\db{0,n-1}$ est atteignable à partir de $i$ si toutes les altitudes entre les indices $k$ (inclus) et $i$ (exclus) sont $\lt \l_i$.

  1. Écrire une fonction largeur_atteignable qui prend en argument la liste l et l'indice $i$, et renvoie le nombre d'indices atteignables à partir de $i$.
  2. ★ Écrire une fonction largueur_atteignable_max qui prend en argument la liste l et renvoie la valeur maximale renvoyée par la fonction précédente
    1. avec une complexité en $O(n)$
    2. en ne parcourant la liste qu'une seule fois.

4. Exercices

Écrire une fonction extremes qui prend une liste l en argument et renvoie la somme du premier et du dernier élément de l. Si la liste est vide, on renverra 0, et si la liste ne contient qu'un seul élément, on renverra cet élément.

Écrire une fonction produit_scalaire qui prend en argument deux listes de même longueur et renvoie le produit scalaire de ces deux listes. Le produit scalaire des listes $[a_1,\dots,a_n]$ et $[b_1,\dots,b_n]$ est $\sum_{k=1}^n a_k b_k = a_1b_1 + a_2 b_2 + \dots + a_n b_n$.

Écrire une fonction moyenne qui prend en argument une liste d'entiers ou de flottants et qui renvoie la moyenne des éléments de cette liste. On supposera que la liste n'est pas vide.

Écrire une fonction ind_liste qui prend en arguments une liste et un élément e et renvoie la liste des indices auquel cet élément est atteint. assert(ind_liste[-3,5,8,-3], -3) == [0,3])

Écrire une fonction evalue_polynome qui prend en argument une liste $\texttt{l} = [a_0, a_1, \dots,a_n]$ et un flottant $x$ et renvoie la valeur $a_0 + a_1 x + \dots + a_n x^n$.

En utilisant une variable intermédiaire supplémentaire, on proposera une version qui n'utilise pas le calcul de puissance avec **, et qui n'effectue qu'un nombre linéaire d'opérations élémentaires +/*.

Écrire une fonction parite_constante qui prend en argument une liste d'entier et qui renvoie True si tous les éléments de l ont la même parité, et False sinon. Si la liste est vide, on renverra True.

Créer la liste des $100$ premiers nombres de Fibonacci, c'est-à-dire des 100 premiers termes de la suite définie par $F_0=F_1=1$ et $\forall n\in\N,\,F_{n+2} = F_{n+1} + F_n$.

Écrire une fonction somme_listes qui prend deux listes en argument et renvoie une nouvelle liste de taille égale au maximum des deux tailles et dont l'élément d'indice $i$ est la somme des éléments d'indice $i$ des deux listes ; si une des listes n'a pas d'élément d'indice $i$, elle compte comme $0$. Par exemple, somme_listes [1,2] [1,2,3] renverra [2,4,3].

Écrire une fonction cycle qui prend en argument une liste et qui permute cycliquement l'ordre de ses éléments : si l vaut [1,2,3,4], après l'appel cycle(l), l vaudra [2,3,4,1].

La variance $V$ d'une série statistique $x_1,\dots,x_n$ dont la moyenne est $m$ est donnée par la formule $$V = \frac{1}{n} \sum_{i=1}^n (x_i - m)^2 = \frac{1}{n}\left((x_1 - m)^2 + (x_2-m)^2 + \dots + (x_n - m)^2\right).$$ Écrire une fonction variance qui prend en argument une liste non vide d'entiers ou de flottants et qui renvoie la variance de cette liste.

Écrire des fonctions qui prennent une liste d'entiers l en argument et renvoient

  1. la liste formée des éléments pairs de l.
  2. la liste formée des éléments d'indices pairs de l.
  3. la liste des 10 derniers éléments de l. Si la longueur de l est $\lt 10$, renvoyer tous les éléments de l.

La fonction randint du module random (à importer) prend deux arguments entiers a,b et renvoie un entier aléatoire entre a (inclus) et b (exclus).

  1. Écrire une fonction qui renvoie une liste de taille 100 contenant 100 entiers aléatoires compris entre 0 et 99 (inclus).
  2. Écrire une fonction qui prend en argument une liste d'entiers et renvoie le nombre d'éléments de $\db{1,99}$ qui appartiennent à cette liste.
  3. En répétant l'expérience aléatoire, estimer le nombre moyen d’éléments de $\db{1,99}$ distincts obtenus lorsqu'on tire 100 fois un nombre aléatoire entre 0 et 99.
  4. Comparer à la valeur théorique $100 - 100 \left(\frac{99}{100}\right)^{100}$.

  1. Écrire une fonction médiane qui prend une liste d'entiers en argument et renvoie une médiane de cette liste sans trier la liste.

    Si $\texttt{l}$ est de taille $n$, une médiane de $\texttt{l}$ est un élément $m$ de $\texttt{l}$ tel qu'au moins $\frac{n}{2}$ des éléments de $\texttt{l}$ soit $\geq m$, et au moins $\frac{n}{2}$ des éléments soit $\leq m$.

  2. Réécrire une fonction médiane_bis qui utilise la méthode sort. Si l est une liste, l'appel l.sort() trie la liste (donc la modifie).

Écrire une fonction prenant en argument un entier $n$ et renvoyant la liste des entiers $N$ qui peuvent s'écrire d'au moins deux façons différentes comme $N = xy$, où $1\lt x\lt y$ et $x+y \lt n$.

Écrire une fonction triangle qui prend un entier en argument et imprime la figure ci-contre. 

In [1]: triangle(5)
1
23
456
7891
01112

Un couloir est éclairé par 100 bulbes numérotés de 1 à 100. À l'origine, tous les bulbes sont éteints. On commence par actionner tous les interrupteurs. Puis on actionne tous les interrupteurs pairs, à partir du second. Puis on actionne tous les trois interrupteurs, à partir du troisième, et ainsi de suite jusqu'à 100 (compris).

  1. À l'aide de Python, déterminer quels sont les bulbes allumés à la fin.
  2. Conjecturer le résultat si l'on remplace $100$ par $n$ quelconque, et le démontrer.

  1. En utilisant une liste de booléens de taille $n$, implémenter le crible d'Ératosthène et imprimer la liste des nombres premiers inférieurs à $n$.
  2. Quel est le nombre d'opérations élémentaires ?

On considère la suite de Conway dont les premiers termes sont $1, 11, 21, 1211, 111221, \dots$. Chaque terme est obtenu en lisant le précédent à haute voix.

  1. Afficher les 20 premiers termes de la suite de Conway.
  2. Conjecturer et démontrer une propriété remarquable de cette suite.
  3. Étudier expérimentalement la convergence
    1. de la fréquence d'apparition de chaque chiffre dans le $n$−ième terme de la suite de Conway.
    2. du quotient de la longueur du $n$−ième terme par la longueur du précédent.

Les entiers de Hamming sont les entiers naturels qui n'admettent aucun diviseur premier autre que $2,3$ et $5$.

  1. Déterminer le nombre d'entiers de Hamming inférieurs ou égaux à $10^{10}$.
  2. Déterminer le 2000ᵉ nombre de Hamming.

Étant donnée une liste $\texttt{l} = [\l_0,\dots,\l_{n-1}]$ dont les éléments sont des entiers positifs que l'on représente sous la forme d'un histogramme, déterminer l'aire maximale d'un rectangle de côtés entiers posé entre les abscisses $0$ et $n$ qui reste sous la courbe de $\texttt{l}$.